package list;

import java.util.Stack;

/**
 * 题目：判断是否是回文链表
 *  y: 1->2->3->2->1 是回文串
 *
 *
 * @Author Gavin
 * @date 2021.12.18 22:59
 */
public class list_2 {
    /**
     * 第一种方法：
     * 通过一个stack栈进行存储链表的节点，先依次入栈，然后出栈进行比较
     * 这种方法就是需要额外的存储空间
     */
    //Time:O(n) Space:O(n)
    public static boolean solution_1(ListNode head){
        if(head==null||head.next==null)return true;
        Stack<ListNode> stack=new Stack<>();
        ListNode temp=head;
        while (head!=null){
            stack.push(head);
            head=head.next;
        }
        while (temp!=null){
            if(stack.pop()!=temp)return false;
            temp=temp.next;
        }
        return true;
    }

    /**
     * 第二种方法
     * 先翻转一半的list节点，然后从中间往两边走依次进行判断，
     * 这样的方法能够减少空间复杂度
     */
    public static boolean solution_2(ListNode head){
        //首先求出list节点的个数
        int len=0;
        ListNode p=head;
        while (p!=null){
            len++;
            p=p.next;
        }
        //然后对list一半的节点进行翻转
        ListNode cur=head,pre=null;
        for (int i=0;i<len/2;++i){
            ListNode temp=cur.next;
            cur.next=pre;
            pre=cur;
            cur=temp;
        }
        System.out.println(cur.val);
        //如果len为奇数的话，cur需要往后面移动一位
        /**
         * y:  1 2 3 2 1
         *  上面的链表翻转到3这里
         *  2->1  3->2->1   此时是这样的状态,cur指向3这个节点,所以此时cur就需要移动到下一个节点
         *  就变为这样的两个链表进行比较
         *  2->1  3  2->1   3是公有的所以直接遍历其它元素就行
         */
        if(len%2==1)cur=cur.next;

        while (cur!=null&&pre!=null){
            if(pre.val!=cur.val)return false;
            cur=cur.next;
            pre=pre.next;
        }
        return true;
    }

    public static void main(String[] args) {
        ListNode p1=new ListNode();
        ListNode p2=new ListNode();
        ListNode p3=new ListNode();
        p1.val=1;
        p1.next=p2;
        p2.val=2;
        p2.next=p3;
        p3.val=1;
        System.out.println(solution_2(p1));
    }
}
